{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Groups to Create a Valid Assignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minGroupsForValidAssignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #合法分组的最少组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code>&nbsp;下标从 <strong>0</strong>&nbsp;开始的整数数组&nbsp;<code>nums</code>&nbsp;。</p>\n",
    "\n",
    "<p>我们想将下标进行分组，使得&nbsp;<code>[0, n - 1]</code>&nbsp;内所有下标&nbsp;<code>i</code>&nbsp;都 <strong>恰好</strong> 被分到其中一组。</p>\n",
    "\n",
    "<p>如果以下条件成立，我们说这个分组方案是合法的：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>对于每个组&nbsp;<code>g</code>&nbsp;，同一组内所有下标在&nbsp;<code>nums</code>&nbsp;中对应的数值都相等。</li>\n",
    "\t<li>对于任意两个组&nbsp;<code>g<sub>1</sub></code> 和&nbsp;<code>g<sub>2</sub></code>&nbsp;，两个组中&nbsp;<strong>下标数量</strong> 的&nbsp;<strong>差值不超过&nbsp;</strong><code>1</code>&nbsp;。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回一个整数，表示得到一个合法分组方案的 <strong>最少</strong>&nbsp;组数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [3,2,3,2,3]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>一个得到 2 个分组的方案如下，中括号内的数字都是下标：\n",
    "组 1 -&gt; [0,2,4]\n",
    "组 2 -&gt; [1,3]\n",
    "所有下标都只属于一个组。\n",
    "组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。\n",
    "组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。\n",
    "组 1 中下标数目为 3 ，组 2 中下标数目为 2 。\n",
    "两者之差不超过 1 。\n",
    "无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。\n",
    "所以答案为 2 。</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>nums = [10,10,10,3,1,1]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>一个得到 2 个分组的方案如下，中括号内的数字都是下标：\n",
    "组 1 -&gt; [0]\n",
    "组 2 -&gt; [1,2]\n",
    "组 3 -&gt; [3]\n",
    "组 4 -&gt; [4,5]\n",
    "分组方案满足题目要求的两个条件。\n",
    "无法得到一个小于 4 组的答案。\n",
    "所以答案为 4 。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-groups-to-create-a-valid-assignment](https://leetcode.cn/problems/minimum-number-of-groups-to-create-a-valid-assignment/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-groups-to-create-a-valid-assignment](https://leetcode.cn/problems/minimum-number-of-groups-to-create-a-valid-assignment/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,2,3,2,3]', '[10,10,10,3,1,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        \n",
    "        cands = Counter(nums).values()\n",
    "        n = len(nums)\n",
    "        \n",
    "        \n",
    "        def helper(size):\n",
    "            res = 0\n",
    "            for cand in cands:\n",
    "                a, b = divmod(cand, size)\n",
    "                if b > a:\n",
    "                    return float('inf')\n",
    "                res += math.ceil(cand / (size + 1))\n",
    "            return res\n",
    "        \n",
    "        ans = n\n",
    "        for size in range(1, min(cands)+1):\n",
    "            ans = min(ans, helper(size))\n",
    "        \n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        def spl(left,right,num):\n",
    "            n = num//right\n",
    "            for i in range(n,-1,-1):\n",
    "                if (num-right*i)%left == 0:\n",
    "                    return [1,(num-right*i)//left + i]\n",
    "            return [0,0]\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        temp = 1\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                temp += 1\n",
    "            else:\n",
    "                res.append(temp)\n",
    "                temp = 1\n",
    "        res.append(temp)\n",
    "        right = res[0]+1\n",
    "        left = right-1\n",
    "        flag = True\n",
    "        while flag:\n",
    "            flag = False\n",
    "            for num in res:\n",
    "                if spl(left,right,num)[0] == 0:\n",
    "                    right -= 1\n",
    "                    left -= 1\n",
    "                    flag = True\n",
    "                    break\n",
    "        print(right)\n",
    "        ans = 0\n",
    "        for num in res:\n",
    "            ans += spl(left,right,num)[1]\n",
    "            print(num,spl(left,right,num)[1])\n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        li=[]\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count=1\n",
    "        for i in range(1,n):\n",
    "            if nums[i]==nums[i-1]:\n",
    "                count+=1\n",
    "            else:\n",
    "                li.append(count)\n",
    "                count=1\n",
    "        li.append(count)\n",
    "        minm = min(li)+1\n",
    "        res=0\n",
    "        print(li)\n",
    "        for i in range(minm,0,-1):\n",
    "            res=0\n",
    "            flag = True\n",
    "            for x in li:\n",
    "                print(res)\n",
    "                save = x%i\n",
    "                if save==0 or save==i-1:\n",
    "                    res+=math.ceil(x/i)\n",
    "                    continue\n",
    "                    \n",
    "                # save2 = x%(i-1)\n",
    "                # if save2==0:\n",
    "                #     res+=math.ceil(x/(i-1))\n",
    "                ff = False\n",
    "                q = inf\n",
    "                if x%(i-1)==0:\n",
    "                    q=x//(i-1)\n",
    "                # print(x,x,x,q,q,q,q)\n",
    "                p = 0\n",
    "                while x>=(i-1):\n",
    "                    x-=(i-1)\n",
    "                    p+=1\n",
    "                    if x%i==0:\n",
    "                        p+=(x//i)\n",
    "                        ff = True\n",
    "                        break\n",
    "                if ff:\n",
    "                    res+=min(q,p)\n",
    "                    continue\n",
    "                else:\n",
    "                    if q==inf:\n",
    "                        flag=False\n",
    "                    else:\n",
    "                        res+=q\n",
    "                        continue\n",
    "                # break\n",
    "            if flag:\n",
    "                return res\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        arr = []\n",
    "        for v in nums:\n",
    "            if len(arr) == 0 or v != arr[-1][1]:\n",
    "                arr.append([1, v])\n",
    "            else:\n",
    "                arr[-1][0] += 1\n",
    "        \n",
    "        arr.sort()\n",
    "\n",
    "        # print(arr)\n",
    "\n",
    "        res = len(nums)\n",
    "\n",
    "        x = 1\n",
    "        while x <= arr[0][0]:\n",
    "            tmp = 0\n",
    "            f = True\n",
    "            for cnt,val in arr:\n",
    "                b0 = cnt % x\n",
    "                a0 = (cnt - b0) // x - b0\n",
    "                # print(x, cnt, a0, b0)\n",
    "                if a0 < 0:\n",
    "                    f = False\n",
    "                    break\n",
    "                b0 += a0 // (x + 1) * x\n",
    "                a0 %= (x + 1)\n",
    "                tmp += b0 + a0\n",
    "                # print(x, cnt, a0, b0)\n",
    "            \n",
    "            if f:\n",
    "                res = min(tmp, res)\n",
    "            x += 1\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        \"\"\" bisect choose maxLen subarr\"\"\"\n",
    "        values = Counter(nums).values()\n",
    "        def calc(m):\n",
    "            if m == 1:\n",
    "                return True\n",
    "            for v in values:\n",
    "                if not v % m:\n",
    "                    continue\n",
    "                div, mod = divmod(v, m - 1)    \n",
    "                if mod > div:\n",
    "                    return False\n",
    "            return True\n",
    "        if max(values) - min(values) < 2:\n",
    "            return len(values)\n",
    "        l, r = 1, 1 + max(values)\n",
    "        while l <= r:\n",
    "            m = (l + r) >> 1\n",
    "            if calc(m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        print(l, r)\n",
    "        res = 0\n",
    "        for v in values:\n",
    "            res += math.ceil(v / r)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        #这道题有点像是为了出题而出题\n",
    "        #先找到每个相同的数各有多少个\n",
    "        #最小的是k 那么可以是k或者k+1\n",
    "        #a = x//k, b = x % k\n",
    "        #这其中相当于有了 a 个 k个的数组，还省了b\n",
    "        #所以只a>=b，就能保持所有的分组<=k+1\n",
    "        #有一个a<b，那就不行\n",
    "        cnt = collections.Counter(nums)\n",
    "        cnt = [ele for i,ele in cnt.items()]\n",
    "        \n",
    "        k = min(cnt)\n",
    "        for i in range(k,0,-1):\n",
    "            ans = 0\n",
    "            for num in cnt:\n",
    "                div,mod = num//i, num%i\n",
    "                if (div>=mod):\n",
    "                    ans += math.ceil(num/(i+1))\n",
    "                else:\n",
    "                    break\n",
    "            else:\n",
    "                print(i)\n",
    "                return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        a = sorted(Counter(nums).values())\n",
    "        st = set(range(1, a[0] + 1))\n",
    "        def ok(x, y):\n",
    "            if x % y == 0 or x % (y + 1) == 0: return True\n",
    "            return x // (x // y) == y\n",
    "        for x in a:\n",
    "            for y in list(st):\n",
    "                if not ok(x, y): st.remove(y)\n",
    "        y = max(st)\n",
    "        res = 0\n",
    "        for x in a:\n",
    "            res += (x + y) // (y + 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = float('inf')\n",
    "        counter = collections.Counter(nums)\n",
    "        for k in range(min(counter.values()), 0, - 1):\n",
    "            cur = 0\n",
    "            for c in counter.values():\n",
    "                p, q = c // k, c % k \n",
    "                if q > p:\n",
    "                    break \n",
    "                cur += (c + k) // (k + 1)\n",
    "            else:\n",
    "                res = min(res, cur)\n",
    "        return res if res != float('inf') else - 1 \n",
    "\n",
    "\n",
    "\n",
    "       \n",
    "\n",
    "\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        cnt=Counter(nums)\n",
    "        mx=max(cnt.values())\n",
    "        ans=len(nums)\n",
    "        for k in range(mx,1,-1):\n",
    "            res=0\n",
    "            for v in cnt.values():\n",
    "                if v<k-1 or v%(k-1)>v//(k-1):\n",
    "                    res=inf\n",
    "                    break\n",
    "                res+=(v+k-1)//k\n",
    "            ans=min(res,ans)\n",
    "        return ans\n",
    "                \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from bisect import bisect_left, bisect_right, insort_left, insort_right, insort, bisect\n",
    "from math import ceil, floor, pow, gcd, sqrt, log10, fabs, fmod, factorial, inf, pi, e\n",
    "from heapq import heapify, heapreplace, heappush, heappop, heappushpop, nlargest, nsmallest\n",
    "from collections import defaultdict, Counter, deque\n",
    "from itertools import permutations, combinations, combinations_with_replacement, accumulate, count, groupby, pairwise\n",
    "from queue import PriorityQueue, Queue, LifoQueue\n",
    "from functools import lru_cache, cache, reduce\n",
    "from typing import List, Optional\n",
    "import sys\n",
    "\n",
    "from sortedcontainers import SortedList, SortedDict, SortedSet\n",
    "\n",
    "sys.setrecursionlimit(10001000)\n",
    "\n",
    "MOD = int(1e9 + 7)\n",
    "INF = int(1e20)\n",
    "INFMIN = float('-inf')  # 负无穷\n",
    "INFMAX = float('inf')  # 正无穷\n",
    "PI = 3.141592653589793\n",
    "direc = [(1, 0), (0, 1), (-1, 0), (0, -1)]\n",
    "direc8 = [(1, 0), (0, 1), (-1, 0), (0, -1), (1, 1), (1, -1), (-1, 1), (-1, -1)]\n",
    "ALPS = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\n",
    "alps = 'abcdefghijklmnopqrstuvwxyz'\n",
    "\n",
    "'''\n",
    "gcd(), ord(), chr(), lower(), upper() 最大公约数/ASCII字符数值/数值ASCII字符/小写/大写\n",
    "startswith(s), endswith(s), find(), index(), count(s)  字符串是否以s开始的/字符串是否以s结尾的/查找返回的是索引/获取索引\n",
    "isalpha(), isdigit(), space(),join()  判断是否全为字符/判断是否全为数字/判断是否为空格/拼接\n",
    "eval() 字符串转换成列表、元组或者字典/\n",
    "uniform(x, y), pow(x, y)# 随机生成下一个实数，它在[x,y]范围内/ x**y 运算后的值。\n",
    "字典推倒式 {key: len(key) for key in list}\n",
    "列表推倒式 [i for i in range(100) if i % 3 == 0] 可切片,可索引,可重复\n",
    "集合推倒式 {i ** 2 for i in (1, 2, 3)}  不可索引,不可切片,不可重复元素\n",
    "'''\n",
    "\n",
    "# 数值和字母进行转换 ord()函数是把字符转换成ASCII码 chr()函数是把ASCII码转换成字符\n",
    "def alp(i):\n",
    "    return chr(ord('a') + i % 26)  # i=0->'a', i=25->'z'\n",
    "\n",
    "# lcm 最小公倍数 gcd 最大公约数\n",
    "def lcm(x, y):\n",
    "    return x * y // gcd(x, y)\n",
    "\n",
    "# 快速幂\n",
    "def qpow(x, y):\n",
    "    ans = 1\n",
    "    while y:\n",
    "        if y & 1:\n",
    "            ans *= x\n",
    "        x *= x\n",
    "        y >>= 1\n",
    "    return ans\n",
    "\n",
    "# 求组合数\n",
    "def Comb(n, m, p):\n",
    "    a = (factorial(n)) % p\n",
    "    b = (qpow(factorial(m), (p - 2), p)) % p\n",
    "    c = (qpow(factorial(n - m), (p - 2), p)) % p\n",
    "    return a * b * c % p\n",
    "\n",
    "# lucas求组合数\n",
    "def Lucas(n, m, p):\n",
    "    if m == 0:\n",
    "        return 1\n",
    "    return Comb(n % p, m % p, p) * Lucas(n // p, m // p, p) % p\n",
    "\n",
    "def rep():\n",
    "    a = list(map(int, input().split()))\n",
    "    return a\n",
    "\n",
    "def sep():\n",
    "    a = input().rstrip('\\n')\n",
    "    return a\n",
    "\n",
    "# --idea \n",
    "# -*- coding: utf-8 -*-\n",
    "# @Author  : hakusai\n",
    "# @Time    : 2023/10/22 16:08\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        ans = 0\n",
    "        # 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。所以以最小的计数值最为k个一组 大于最小的计数值可以分为k/k+1个一组\n",
    "        # 枚举k (k是计数里面最少的)从大到小 k个为一组\n",
    "        for k in range(min(cnt.values()), 0, -1):\n",
    "            # 从小到大枚举每个值的数量\n",
    "            for c in cnt.values():\n",
    "                q, r = divmod(c, k)\n",
    "                if q < r:\n",
    "                    ans = 0\n",
    "                    break\n",
    "                else:\n",
    "                    ans += (c + k) // (k + 1)\n",
    "            if ans > 0:\n",
    "                return ans\n",
    "        return ans\n",
    "\n",
    "if __name__ == '__main__':\n",
    "    Solution.minGroupsForValidAssignment(self=None, nums=[10,10,10,3,1,1])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        arr = [(cnt[key],key) for key in cnt]\n",
    "        if len(arr)==1:return 1\n",
    "\n",
    "        min_num = float('inf')\n",
    "        for x in arr:min_num = min(min_num,x[0])\n",
    "        def cal_res(min_num):\n",
    "            ans = 0\n",
    "            for x in arr:\n",
    "                if x[0]//(min_num+1)>=min_num-x[0]%(min_num+1):ans+=ceil(x[0]/(min_num+1))\n",
    "                elif x[0]%min_num<=x[0]//min_num:ans+=x[0]//min_num\n",
    "                else:return float('inf')\n",
    "            return ans\n",
    "        res = len(nums)\n",
    "        for x in range(min_num,0,-1):\n",
    "            res = min(res,cal_res(x))\n",
    "            print(x,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minGroupsForValidAssignment(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums) \n",
    "        arr = [(k,v) for k,v in cnt.items()]\n",
    "        arr.sort(key=lambda x : x[1])\n",
    "        def check(k):\n",
    "            for x, y in arr:\n",
    "                if y // k < y % k:\n",
    "                    return False \n",
    "            return True \n",
    "\n",
    "        for k in range(arr[0][1], 0, -1):\n",
    "            if check(k):\n",
    "                tot = 0 \n",
    "                for x, y in arr:\n",
    "                    tot += (y + k) // (k + 1) \n",
    "                break \n",
    "        return tot "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
